package Sequence;

public class Test0123 {
}

class Solution0123_1 {
    public int maxProfit(int[] prices) {
        int buy1=-prices[0],buy2=-prices[0],sell1=0,sell2=0;
        for (int price : prices) {
            buy1=Math.max(-price,buy1);
            sell1=Math.max(sell1,buy1+price);
            buy2=Math.max(buy2,sell1-price);
            sell2=Math.max(sell2,buy2+price);
        }

        return sell2;
    }
}

class Solution123_2 {
    public int maxProfit(int[] prices) {
        int n=4;
        int[] dp = new int[4];
        for (int i = 0; i < n; i+=2) {
            dp[i] = Integer.MIN_VALUE;
        }
        for (int price : prices) {
            for (int i = n-1; i >= 0; i--) {
                if ((1&i)==0) {
                    int lastProfit =i>0?dp[i-1]:0;
                    dp[i] = Math.max(dp[i],lastProfit-price);
                } else {
                    dp[i] = Math.max(dp[i],dp[i-1]+price);
                }
            }
        }

        return dp[3];
    }
}